// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-27 21:15
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DynamicPlan.threeLeafTrains;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class FindNumberOfLIS {
    /**
     * 最长递归子序列个数  二分查找进行定位
     */
    public int findNumberOfLIST(int[] nums) {
        /*
            1 状态定义&&状态转移：
                   每一个元素存在两个状态:
                   当前元素在最优解中，找到最接近当前值的数字idx(可以使用TreeSet的Ceiling？)
                   f[i][1] = f[idx][1]+1
                   当前元素不在最优解中,
                   f[i][0] = Math.max(f[i-1][0],f[i-1][1])
                   初始状态定义：
                   f[0][0] = 0;f[0][1] = 1;
            2 结果输出
                  遍历状态数组，记录max的数值，max = Math.max(f[n-1][0],f[n-1][1])
         */
        int n = nums.length, res = 0;
        int[][] f = new int[n][2];
        f[0][0] = 0;
        f[0][1] = 1;
        TreeSet<Integer> set = new TreeSet<>();
        Map<Integer, Integer> map = new HashMap<>();
        set.add(nums[0]);
        map.put(nums[0], 1);
        for (int i = 1; i < n; i++) {
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = 1;
            Integer ceiling = set.floor(nums[i] - 1);
            if (ceiling != null) {
                f[i][1] = Math.max(f[i][1], map.get(ceiling) + 1);
            }
            set.add(nums[i]);
            map.put(nums[i], f[i][1]);
        }
        int max = Math.max(f[n - 1][0], f[n - 1][1]);
        for (int i = 0; i < n; i++) {
            if (f[i][1] == max) {
                res++;
            }
        }
        return res;
    }

    /**
     * 寻找的是最大上升字串的数目，不是长度，需要增加一维存储当前长度的次数
     */
    public int findNumberOfLISTT(int[] nums) {
        /*-----变量初始化-----*/
        int n = nums.length, max = 1;
        int[] g = new int[n], f = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    // i可以放在j前面
                    if (f[i] < f[j] + 1) {
                        f[i] = f[j] + 1;
                        g[i] = g[j];
                    } else if (f[i] == f[j] + 1) {
                        // 不用赋值，直接相等，因为前面已经出现过相同长度的升序字串
                        // 1386 ->138 + 136 -> 1 + 1 = 2
                        g[i] += g[j];
                    }
                }
            }
            max = Math.max(max, f[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (f[i] == max) {
                ans += g[i];
            }
        }
        return ans;
    }

    int n;
    int[][] tr = new int[2010][2];

    int lowbit(int x) {
        return x & -x;
    }

    int[] query(int x) {
        /**
         * len:当前索引元素可以工程的上升序列的长度
         * cnt: 表示当前元素可以构成当前长度上升序列的个数
         */
        int len = 0, cnt = 0;
        /*
            数组序号0的左边不存在元素，所以元素查找在0-x之间
         */
        for (int i = x; i > 0; i -= lowbit(i)) {
            if (len == tr[i][0]) {
                /*
                    等于说明构成len长度的字串方法前面出现过
                 */
                cnt += tr[i][1];
            } else if (len < tr[i][0]) {
                /*
                    小于说明，当前长度的字数组是第一次出现
                 */
                len = tr[i][0];
                cnt = tr[i][1];
            }
        }
        return new int[]{len, cnt};
    }

    /*
        通过query方法查询到当前元素的len和cnt，通过add方法实现当前索引元素的树状数组更新
        一般的树状数组的c[]数组是一维的，但是题解里采用的是二维数组，是为了存储当前子树中的LIS
        add是添加当前元素可以构成的LIS长度和个数，并且由于树状数组的关系，当前元素a[]会影响很多c[]，所以当
        加入元素的时候，需要更新会产生影响的c[]，时间复杂度为O(lgN);c[]数组中存放的是最大的len和cnt,
        这就是为什么树状数组可以在O(lgN)的时间范围内实现最大数据的查询
     */
    void add(int x, int[] info) {
        for (int i = x; i <= n; i += lowbit(i)) {
            int len = tr[i][0], cnt = tr[i][1];
            if (len == info[0]) {
                cnt += info[1];
            } else if (len < info[0]) {
                len = info[0];
                cnt = info[1];
            }
            tr[i][0] = len;
            tr[i][1] = cnt;
        }
    }

    public int findNumberOfLIS(int[] nums) {
        n = nums.length;
        // 离散化
        int[] tmp = nums.clone();
        Arrays.sort(tmp);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0, idx = 1; i < n; i++) {
            if (!map.containsKey(tmp[i])) {
                map.put(tmp[i], idx++);
            }
        }
        // 树状数组维护 (len, cnt) 信息
        for (int i = 0; i < n; i++) {
            // x 是离散化之后数据的索引位置，索引序号区间为[1-n]
            /*
                为什么可以通过树状数组实现升序子序列长度的计算？
                tr[][] 数组在初始化的时候全部数据都是0，而进行构成字串查询的时候使用的是原数组中的元素，而不是离散化之后的升序数组
                通过原数组的在树状数组中的索引，可以从当前位置往前面找，如果出现长度大于等于当前长度的元素，则更新数值，而那些小于当前元素
                的数值，根据原数组的原始顺序，实在当前元素的访问顺序之后，所以可以更新当前元素的都是在原数组中当前元素的左边，并且小于当前元素；
                因为大于当前元素的数据索引都在右边
             */
            int x = map.get(nums[i]);
            /*
                一共有五个数据，使用的是树状数组实现对数据查找和添加，时间复杂度为O(lgN)
             */
            int[] info = query(x - 1);
            /*
                获取当前索引元素的构成上升序列的长度和数量，并且在树状数组中更新，时间复杂度为O(lgN)
                获取的len和cnt是小于当前元素索引的元素所构成的最长字串和方法（刚好配对LIS条件）
             */
            int len = info[0], cnt = info[1];
            /*
                每一个单独的元素可以构成一个最小上升子数组，cnt为0的时候存在于前面没有元素或者没有比当前元素小的元素
             */
            add(x, new int[]{len + 1, Math.max(cnt, 1)});
        }
        /*
            为什么query(n)就是答案？
                因为数组已经预处理过，在离散化的时候已经实现了排序，tr[][]数组中存取的状态就是根据离散化的数值进行状态存储的
                当前数组的最长升序子序列的尾端一定是数组中的最大值,当tr记录的数据是len,cnt；其中cnt记录了当前状态下的构成数量
         */
        int[] ans = query(n);
        return ans[1];
    }


    @Test
    public void shout() {
        int[] nums = {1, 3, 5, 4, 7};
//        int[] nums = {2, 2, 2, 2, 2};
        System.out.println(findNumberOfLIS(nums));
    }
}
